package leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class _128_LongestConsecutiveSequence {
    public static void main(String[] args) {
        Solution solution = new _128_LongestConsecutiveSequence().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // O(nlogn)
    class Solution1 {
        public int longestConsecutive(int[] nums) {
            if (nums.length == 0) return 0;
            Arrays.sort(nums);
            int res = 1, len = 1;
            int prev = nums[0];
            for (int i = 1; i < nums.length; i++) {
                int cur = nums[i];
                if (cur == prev) {
                    continue;
                } else if (cur == prev + 1) {
                    len++;
                    prev = cur;
                    res = Math.max(len, res);
                } else {
                    len = 1;
                    prev = cur;
                }
            }
            return res;
        }
    }

    // O(n)
    class Solution {
        public int longestConsecutive(int[] nums) {
            int res = 0;
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }

            for (int num : set) {
                if (set.contains(num - 1)) {
                    continue;
                }
                int curNum = num;
                int curLen = 1;
                while (set.contains(curNum + 1)) {
                    curNum++;
                    curLen++;
                }
                res = Math.max(res, curLen);
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}